/*
【题目描述】
Pell数列a1,a2,a3,...
的定义是这样的，a1=1,a2=2,...,an=2an−1+an−2(n>2)
。

给出一个正整数k，要求Pell数列的第k项模上32767是多少。

【输入】
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1≤k<1000000)。

【输出】
n行，每行输出对应一个输入。输出应是一个非负整数。

【输入样例】
2
1
8
【输出样例】
1
408
*/

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k;
	vector<int> vk;
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> k;
		vk.push_back(k);
	}
	for(size_t i=0; i<vk.size(); ++i) {
		k = vk[i];
		long n1=1, n2=2;
		if(k==1) {
			cout << n1 << endl;
		}
		else if(k==2) {
			cout << n2 << endl;
		}
		else {
			int n=0;
			for(int i=3; i<=k; ++i) {
				n = (2*n2 + n1)%32767;
				n1 = n2;
				n2 = n;
			}
			cout << n << endl;
		}
	}
	return 0;
}
